package com.study.daily.algozuo.y2021.m10.day1128;

/**
 * Nways
 *
 * @author Tom on 2021/11/28
 */
public class Code01_Nways {
    public static void main(String[] args) {
        Code01_Nways nways = new Code01_Nways();
        int ways1 = nways.ways1(5, 2, 4);
        int ways2 = nways.way2(5, 2, 4);
        int ways3 = nways.ways3(5, 1, 3, 4);
        System.out.println(ways1);
        System.out.println(ways2);
        System.out.println(ways3);
//        int[][] arr = new int[3][4];
//        System.out.println(arr.length);
    }

    public int ways1(int N, int aim, int n) {
        return process1(0, n, aim, N);
    }

    public int process1(int cur, int rest, int aim, int N) {
        if (rest == 0) {
            return cur == aim ? 1 : 0;
        }
        if (cur == 0) {
            return process1(1, rest - 1, aim, N);
        }
        if (cur == N - 1) {
            return process1(N - 2, rest - 1, aim, N);
        }
        return process1(cur - 1, rest - 1, aim, N) + process1(cur + 1, rest - 1, aim, N);
    }

    public int way2(int N, int aim, int n) {
        int[][] dp = new int[N][n + 1];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = -1;
            }
        }
        return process2(0, n, aim, N, dp);
    }

    public int process2(int cur, int rest, int aim, int N, int[][] dp) {
        if (dp[cur][rest] != -1) {
            return dp[cur][rest];
        }
        // 如果上面没有计算出结果
        int ans = 0;
        if (rest == 0) {
            ans = cur == aim ? 1 : 0;
            dp[cur][rest] = ans;
            return ans;
        }
        if (cur == 0) {
            dp[cur][rest] = process2(1, rest - 1, aim, N, dp);
            ans = dp[cur][rest];
            return ans;
        }
        if (cur == N - 1) {
            dp[cur][rest] = process2(N - 2, rest - 1, aim, N, dp);
            ans = dp[cur][rest];
            return ans;
        }
        dp[cur][rest] = process2(cur - 1, rest - 1, aim, N, dp) + process2(cur + 1, rest - 1, aim, N, dp);
        ans = dp[cur][rest];
        return ans;
    }

    public  int ways3(int N, int start, int aim, int K) {
        if (N < 2 || start < 1 || start > N || aim < 1 || aim > N || K < 1) {
            return -1;
        }
        int[][] dp = new int[N + 1][K + 1];
        dp[aim][0] = 1;
        for (int rest = 1; rest <= K; rest++) {
            dp[1][rest] = dp[2][rest - 1];
            for (int cur = 2; cur < N; cur++) {
                dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
            }
            dp[N][rest] = dp[N - 1][rest - 1];
        }
        return dp[start][K];
    }


}
